NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part2/13155

Internet Message Format | 1996-08-05 | 2.7 KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.lang.c
Subject: Re: Recursion
Date: Thu, 04 Apr 96 22:43:30 GMT
Organization: none
Message-ID: <[e-mail]>
References: <[e-mail]> <[e-mail]> <4k10q0$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4k10q0$[e-mail]>
           [e-mail] "Jeremy Markman" writes:

>Lawrence Kirby ([e-mail]) wrote:
>
>: I think you've picked a bad example. You really need an extra argument in
>: this case to pass on a running accumulator. A more suitable problem would
>: be to write a recursive function that is passed an integer (unsigned is
>: easiest) and writes the character representation to stdout.
>Absolutely WRONG.  The whole point of recursion is that you do not need a
>running accumulator.

Recursion is a powerful method of formulating, expressing and
indeed solving problems. Running accumulators are a useful and commonly used
technique for dealing with such problems in recursion and functional
languages.

> When written correctly, the return value of each
>recursive loop will be the correct accumulated value.  ANyhow, here is a
>better version of what I already posted...

It is a good idea to compile and test your code before posting it. What you
posted before simply doesn't work (at least not the recursive version).

>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>#include <math.h>
>
>int convert(char *string)
> {
>  int value;
>  int len = strlen(string);
>
>  if (string[0] == '\0')
>    return(0);
>  value = convert(string+1);
>  value += ((string[0] - '0') * pow(10,len-1));
>  return(value);
> }

Really you've proved my point. You've had to resort to an iterative scan
of the string (strlen) which makes this algorithm O(N*N) on the string length.
You've also had to use a heavyweight floating point function (pow) which
may not give accurate results. Using an accumuator would have produced
a far better algorithm and still be very much in the spirit of recursion.

OK, I accept that this problem can be solved without an accumulator but the
lengths you've had to go to to do so are unreasonable, and certainly show
recursion in an unfairly negative light.

>void main()

Results in undefined behavious - use:

int main(void)

> {
>  char *string = "1234";
>
>  printf("%d\n",convert(string));
> }
>

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------